/************************************************************************

								Heroes IV
					  Copyright 2000, The 3DO Company

	------------------------------------------------------------------
  						       rational.h

	$Header: /game/rational.h $

	$NoKeywords: $

 ************************************************************************/

#if !defined( RATIONAL_H_INCLUDED )
#define RATIONAL_H_INCLUDED

#include <cassert>

template < typename t_int >
class t_rational;

// -----------------------------------------------------------------------
// greatest_common_divisor() function template
// -----------------------------------------------------------------------

template < typename t_int >
t_int greatest_common_divisor( t_int first, t_int second )
{
	if ( first < 0 )
		first = -first;
	if ( second < 0 )
		second = -second;

	while ( second != 0 )
	{
		t_int remainder = first % second;

		first = second;
		second = remainder;
	}

	return first;
}

// -----------------------------------------------------------------------
// least_common_multiple() function template
// -----------------------------------------------------------------------

template < typename t_int >
inline t_int least_common_multiple( t_int first, t_int second )
{
	return first * ( second / greatest_common_divisor( first, second ) );
}

// -----------------------------------------------------------------------
// Details namespace
// -----------------------------------------------------------------------

namespace rational_details
{

	// -----------------------------------------------------------------------
	// -----------------------------------------------------------------------
	template < typename t_int >
	bool less_than_helper( t_rational< t_int > const & left, t_rational< t_int > const & right )
	{
		t_int gcd1 = greatest_common_divisor< t_int >( left.numerator(), right.numerator() );
		t_int gcd2 = greatest_common_divisor< t_int >( left.denominator(), right.denominator() );
		return		( left.numerator() / gcd1 ) * ( right.denominator() / gcd2 )
				<	( right.numerator() / gcd1 ) * ( left.denominator() / gcd2 );
	}

} // Details namespace

// -----------------------------------------------------------------------
// t_rational class template - representation of a rational number.
// Always stored in normalized form.  The denominator is always positive.
// -----------------------------------------------------------------------

template < typename t_int >
class t_rational
{
public:
	// Constructors
	t_rational( t_int initial_value = 0 );
	t_rational( t_int numerator, t_int denominator );

	template < typename t_other_int >
	t_rational( t_rational< t_other_int > const & other )
		:	m_numerator( other.numerator() ),
			m_denominator( other.denominator() )
	{
		normalize();
	}

	t_rational( t_rational const & other );

	// Member functions
	t_int denominator() const;
	t_int numerator() const;

	// Operators
	t_rational & operator++();
	t_rational operator++( int );
	t_rational & operator--();
	t_rational operator--( int );

	t_rational & operator+=( t_rational const & other );
	t_rational & operator-=( t_rational const & other );
	t_rational & operator*=( t_rational const & other );
	t_rational & operator/=( t_rational const & other );

private:
	// Types
	struct t_no_normalize {};

	// Data members
	t_int	m_numerator;
	t_int	m_denominator;

	// Constructor
	t_rational( t_no_normalize, t_int numerator, t_int denominator );

	// Member functions
	void normalize();

	// Friend functions
	friend bool operator==( t_rational const & left, t_rational const & right )
	{
		return left.m_numerator == right.m_numerator && left.m_denominator == right.m_denominator;
	}

	friend bool operator!=( t_rational const & left, t_rational const & right )
	{
		return !( left == right );
	}

	friend bool operator<( t_rational const & left, t_rational const & right )
	{
		return rational_details::less_than_helper( left, right );
	}

	friend bool operator>( t_rational const & left, t_rational const & right )
	{
		return right < left;
	}

	friend bool operator<=( t_rational const & left, t_rational const & right )
	{
		return !( left > right )
	}

	friend bool operator>=( t_rational const & left, t_rational const & right )
	{
		return !( left < right );
	}

	friend t_rational operator+( t_rational const & left, t_rational const & right )
	{
		t_rational result = left;
		return result += right;
	}

	friend t_rational operator-( t_rational const & left, t_rational const & right )
	{
		t_rational result = left;
		return result -= right;
	}

	friend t_rational operator*( t_rational const & left, t_rational const & right )
	{
		t_rational result = left;
		return result *= right;
	}

	friend t_rational operator/( t_rational const & left, t_rational const & right )
	{
		t_rational< t_int > result = left;
		return result /= right;
	}

	friend t_rational operator-( t_rational const & arg );
	friend t_rational reciprocal( t_rational const & arg );
};

template < typename t_int >
inline t_rational< t_int >::t_rational( t_int initial_value )
	:	m_numerator( initial_value ),
		m_denominator( 1 )
{
}

template < typename t_int >
inline t_rational< t_int >::t_rational( t_int numerator, t_int denominator )
	:	m_numerator( numerator ),
		m_denominator( denominator )
{
	normalize();
}

template < typename t_int >
inline t_rational< t_int >::t_rational( t_rational const & other )
	:	m_numerator( other.m_numerator ),
		m_denominator( other.m_denominator )
{
}

template < typename t_int >
inline t_rational< t_int >::t_rational( t_no_normalize, t_int numerator, t_int denominator )
	:	m_numerator( numerator ),
		m_denominator( denominator )
{
	assert( m_denominator > 0 );
	assert( greatest_common_divisor< t_int >( m_numerator, m_denominator ) == 1 );
}

template < typename t_int >
inline t_int t_rational< t_int >::denominator() const
{
	return m_denominator;
}

template < typename t_int >
inline t_int t_rational< t_int >::numerator() const
{
	return m_numerator;
}

template < typename t_int >
inline t_rational< t_int > & t_rational< t_int >::operator++()
{
	m_numerator += m_denominator;
	return *this;
}

template < typename t_int >
inline t_rational< t_int > t_rational< t_int >::operator++( int )
{
	t_rational result = *this;
	++*this;
	return result;
}

template < typename t_int >
inline t_rational< t_int > & t_rational< t_int >::operator--()
{
	m_numerator -= m_denominator;
	return *this;
}

template < typename t_int >
inline t_rational< t_int > t_rational< t_int >::operator--( int )
{
	t_rational result = *this;
	--*this;
	return result;
}

template < typename t_int >
t_rational< t_int > & t_rational< t_int >::operator+=( t_rational< t_int > const & other )
{
	t_int new_denominator = least_common_multiple< t_int >( m_denominator, other.m_denominator );
	m_numerator = m_numerator * ( new_denominator / m_denominator ) + other.m_numerator * ( new_denominator / other.m_denominator );
	m_denominator = new_denominator;
	normalize();
	return *this;
}

template < typename t_int >
t_rational< t_int > & t_rational< t_int >::operator-=( t_rational< t_int > const & other )
{
	t_int new_denominator = least_common_multiple< t_int >( m_denominator, other.m_denominator );
	m_numerator = m_numerator * ( new_denominator / m_denominator ) - other.m_numerator * ( new_denominator / other.m_denominator );
	m_denominator = new_denominator;
	normalize();
	return *this;
}

template < typename t_int >
t_rational< t_int > & t_rational< t_int >::operator*=( t_rational< t_int > const & other )
{
	t_int gcd1 = greatest_common_divisor< t_int >( m_numerator, other.m_denominator );
	t_int gcd2 = greatest_common_divisor< t_int >( other.m_numerator, m_denominator );
	m_numerator = ( m_numerator / gcd1 ) * ( other.m_numerator / gcd2 );
	m_denominator = ( m_denominator / gcd2 ) * ( other.m_denominator / gcd1 );
	return *this;
}

template < typename t_int >
t_rational< t_int > & t_rational< t_int >::operator/=( t_rational< t_int > const & other )
{
	assert( other.m_numerator != 0 );
	t_int gcd1 = greatest_common_divisor< t_int >( m_numerator, other.m_numerator );
	t_int gcd2 = greatest_common_divisor< t_int >( m_denominator, other.m_denominator );
	m_numerator = ( m_numerator / gcd1 ) * ( other.m_denominator / gcd2 );
	m_denominator = ( m_denominator / gcd2 ) * ( other.m_numerator / gcd1 );
	return *this;
}

template < typename t_int >
void t_rational< t_int >::normalize()
{
	assert( m_denominator != 0 );

	t_int gcd = greatest_common_divisor< t_int >( m_numerator, m_denominator );
	m_numerator /= gcd;
	m_denominator /= gcd;
	if ( m_denominator < 0 )
	{
		m_numerator = -m_numerator;
		m_denominator = -m_denominator;
	}
}

// -----------------------------------------------------------------------
// Free functions for t_rational class template
// -----------------------------------------------------------------------

template < typename t_int >
inline t_rational< t_int > operator+( t_rational< t_int > const & arg )
{
	return arg;
}

template < typename t_int >
inline t_rational< t_int > operator-( t_rational< t_int > const & arg )
{
	return t_rational< t_int >( t_rational< t_int >::t_no_normalize(), -arg.m_numerator, arg.m_denominator );
}

template < typename t_result, typename t_int >
t_result as( t_rational< t_int > const & arg )
{
	return t_result( arg.numerator() ) / arg.denominator();
}

template < typename t_int >
inline t_rational< t_int > reciprocal( t_rational< t_int > const & arg )
{
	assert( arg.m_numerator != 0 );

	t_int new_numerator = arg.m_denominator;
	t_int new_denominator = arg.m_numerator;
	if ( arg.m_numerator < 0 )
	{
		new_numerator = -new_numerator;
		new_denominator = -new_denominator;
	}
	return t_rational< t_int >( t_rational< t_int >::t_no_normalize(), new_numerator, new_denominator );
}

template < typename t_int >
inline t_int round_toward_zero( t_rational< t_int > const & arg )
{
	return arg.numerator() / arg.denominator();
}

template < typename t_int >
t_int round_away_from_zero( t_rational< t_int > const & arg )
{
	t_int result = arg.numerator() / arg.denominator();
	if ( arg.numerator() % arg.denominator() != 0 )
	{
		if ( arg.numerator() >= 0  )
			++result;
		else
			--result;
	}
	return result;
}

template < typename t_int >
t_int round_up( t_rational< t_int > const & arg )
{
	t_int result = arg.numerator() / arg.denominator();
	if ( arg.numerator() > 0 )
	{
		if ( arg.numerator() % arg.denominator() != 0 )
			++result;
	}

	return result;
}

template < typename t_int >
t_int round_down( t_rational< t_int > const & arg )
{
	t_int result = arg.numerator() / arg.denominator();
	if ( arg.numerator() < 0 )
	{
		if ( arg.numerator() % arg.denominator() != 0 )
			--result;
	}

	return result;
}

template < typename t_int >
t_int round_to_nearest( t_rational< t_int > const & arg )
{
	t_int result = arg.numerator() / arg.denominator();
	t_int remainder = arg.numerator() % arg.denominator();
	if ( arg.numerator() >= 0 )
	{
		assert( remainder >= 0 );
		if ( remainder * 2 >= arg.denominator() )
			++result;
	}
	else
	{
		assert( remainder <= 0 );
		if ( -( remainder * 2 ) > arg.denominator() )
			--result;
	}
	return result;
}

#endif // !defined( RATIONAL_H_INCLUDED )
